class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        '''
        对于每个节点 x，都定义三种颜色值（状态值）：
        0：节点 x 尚未被访问到。
        1：节点 x 正在访问中，dfs(x) 尚未结束。
        2：节点 x 已经完全访问完毕，dfs(x) 已返回。
        '''
        g = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            g[b].append(a)
        
        colors = [0] * numCourses
        # 返回 True 表示找到了环
        def dfs(x: int) -> bool:
            colors[x] = 1 # x 正在访问中
            for y in g[x]:
                if colors[y] == 1 or colors[y] == 0 and dfs(y):
                    return True # 找到了环
            colors[x] = 2 # x 完全访问完毕
            return False # 没有找到环
        
        for i, c in enumerate(colors):
            if c == 0 and dfs(i):
                return False # 有环
        return True